package leetcode_ago.bin_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。
 * 树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度
 * 思路：二叉树最左侧节点编号和最右侧节点编号差值+1就是最大宽度
 * //此时我们在层序遍历的过程中会存储每个出现的节点和他的编号
 * //可以创建一个新的类带编号存储节点【默认的TreeNode不带编号】
 * //即将节点二次包装，新增一个该节点的值
 */
public class Num662_MaxWidth {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        int maxWidth=0;
        Queue<NodeWithNum> queue=new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));
        while(!queue.isEmpty()){
            //当前层宽度
            int levelWidth=0;
            //最左侧节点编号
            int L=0;
            //最右侧节点编号
            int R=0;
            //当前层元素个数
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                NodeWithNum cur=queue.poll();
                if(i==0){
                    L=cur.num;
                }
                if(i==size-1){
                    R=cur.num;
                }
                if (cur.node.left!=null){
                    queue.offer(new NodeWithNum(cur.node.left,cur.num*2));
                }
                if(cur.node.right!=null){
                    queue.offer(new NodeWithNum(cur.node.right,cur.num*2+1));
                }
            }
            levelWidth=R-L+1;
            maxWidth=Math.max(maxWidth,levelWidth);
        }
        return maxWidth;
    }
    private class NodeWithNum{
        TreeNode node;
        //每个二叉树的节点编号
        int num;

        public NodeWithNum(TreeNode node, int num) {
            this.node = node;
            this.num = num;
        }
    }
}
